

#!/usr/bin/env ruby

#require "profile" # Profiling

# Implementacion en Ruby de una rutina que intenta resolver problemas de regresion numerica mediate la tecnica de Programacion Genetica.

# Partiendo de una serie de simbolos, datos y parametros especificados por el usuario el programa trata de encontrar una ecuacion matematica que relaccione una tabla de datos de entrada con los de salida. 
# Por ejemplo: si especificamos las entradas x=0,1,2 y salidas f(x)=1,2,3 el sistema nos deberia encontrar la ecuacion x+1.

# Referencias:

# Programacion Genetica: www.genetic-programming.org.
# Lenguage de programacion Ruby: http://www.ruby-lang.org/.

# Problemas conocidos:  

# ISSUE 1
# gpsystem. 
# Problemas con la presicion. 
# Ruby utiliza la constante Infinity al realizar operaciones que sobrepasan la precision. Y NaN al realizar operaciones entre Infinity.

# ISSUE 2
# cruzarCodigos
# No se consige una buena aleatoriedad en los cruces lo que provoca poblaciones con muchos individuos repetidos afectando por tanto a la convergencia.

# ISSUE 3
# gpsystem
# La impementacion solo permite que el codigo de los individuos tenga un tamaño constante

# ISSUE 4
# gpsystem
# Implementacion realizada para un unico parametro de entrada.

# Estructuras que definen a individuo, simbolos, datos y parametros.

Tindividuo = Struct.new( :codigo, :evaluacion, :error )
Tsimbolos = Struct.new( :funciones, :variables, :numeros )
Tdatos = Struct.new( :entradas, :salidas ) 
Tparametros = Struct.new( :noperandos, :nindividuos, :niteraciones)

# Especificacion del problema de regresion numerica e inicializaciones del sistema.
# Inicializacion de las funciones, variables, valores numericos.

simbolos = Tsimbolos.new( ['+','-','*','/'],                                # funciones.
                          ['x'],                                                 # variables.
                          [0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0] ) # numeros.

# Inicializacion de datos con los valores de entrada y salida.

datos = Tdatos.new( [0,1,2],   # entradas.
                    [1,2,3] ) # salidas

# Inicializacion de los parametros numero de operandos, individuos e iteraciones.

parametros = Tparametros.new( 2,     # noperandos.
                              50,  # nindividuos.
                              10 )  # niteraciones.

# Funciones auxiliares.9

class Fixnum
  # Proteccion de la division entera. 
  # Redefiniendo el metodo / en la clase de los numeros enteros para devolver el valor 1 cuando el denominador sea igual 0.
  alias div /
  def / ( denominador )
    if denominador == 0
      1
    else
      # Si queremos numeros reales el denominador ha de ser real.
      self.div denominador.to_f
    end
  end
end

def randTerm( variables, numeros )
  # Funcion que devuelve aleatoriamente una simbolo terminal. 
  # Uno de entre las variables y los numeros.
  case rand( 2 )
  when 0
    variables[rand( variables.size )]
  when 1
    numeros[rand( numeros.size )].to_s
  end
end

def randFunc( funciones )
  # Funcion que devuelve aleatoriamente un simbolo no terminal. 
  # Uno de entre las funciones.
  funciones[rand( funciones.size )]
end

def generarCodigo( noperandos, funciones, variables, numeros)
  # Funcion que devuelve un vector que contiene de manera alternada n operadores y operandos.
  codigo = Array.new()
  # Ajuste de la longitudo del vector que contendra el codigo para garantizar la alternancia de operadores y operandos.
  longitud = noperandos + noperandos - 1
  # Alterna la inserccion de variables, terminales y funciones.
  longitud.times{ |i|
    if ( i % 2 == 0 ) # Posicion par.
      codigo.push( randTerm( variables, numeros ) )
    else # Posicion impar.
      codigo.push( randFunc( funciones ) )
    end
  }
  codigo
end

def mutarCodigo( codigo, funciones, variables, numeros )
  # Reemplaza aleatoriamente una componente del codigo por otra de la misma clase.
  indice = rand( codigo.size )   # Eleccion al azar de un elemento del codigo a mutar.
  if ( indice % 2 == 0 )  # Indice par
    codigo[indice] = randTerm( variables, numeros )
  else  # Indice impar
    codigo[indice] = randFunc( funciones )
  end
  codigo
end

def cruzarCodigos( codigo1, codigo2 )
  # Funcion que cruza de maneara aleatoriamente dos codigos manteniendo la longitud.
  posicion = rand( codigo1.size ) # Punto de cruce
  elementos = rand( codigo1.size - posicion ) + 1 # Numero de elementos a cruzar
  elementos.times{ |i| codigo2[i+posicion] = codigo1[i+posicion] }
  codigo2
end

def evaluarInd( codigo, evaluacion, variables ,entradas )
  # Evalua a un individuo sustituyendo cada variable por su valor de entrada.
  # NOTA: En este caso solo consideraremos que tenemos una unica variable de entrada.
  evaluacion.each{ |resultado| resultado=0 }  # Reseteo de evaluaciones anteriores.
  entradas.each_index{ |i| # Para cada variable de entrada.
    programa = codigo.to_s
    # Sustituimos la variable por su valor y ejecutamos la ristra resultante.
    begin
      evaluacion[i] = eval( programa.tr( variables.first, entradas[i].to_f.to_s) )
    rescue
      puts "evaluarInd... #{i} #{evaluacion[i]}"
    end
  }
end

def nivelarInd( evaluacion, error, salidas )
  # Funcion de fitness!
  # Devuelve el error calculado conforme a los resultados de las evaluaciones y las salidas esperadas.
  # Reseteo de las aptitudes anteriores.
  error = 0
  salidas.each_index{ |i| # Para cada salida...
    begin
      error += ( salidas[i] - evaluacion[i] ).abs # Calculo de las diferencias absolutas
    rescue
      puts "nivelarInd...error #{error} salidas #{salidas} evaluacion #{evaluacion}"
    end
  }
  if ( !error.to_f.finite? )  # En el caso de exeder la precision...
    error = 9**10
  end
  error
end

# Rutina principal

def gpsystem ( simbolos, datos, parametros )
  ### Creacion aleatoria de una poblacion inicial de n programas formados por funciones, variables y numeros.
  poblacion = Array.new( parametros.nindividuos, Tindividuo){ 
    Tindividuo.new( generarCodigo( parametros.noperandos, simbolos.funciones, simbolos.variables, simbolos.numeros ), Array.new( datos.salidas.size ), 1 )
  }
  
  iterIniciales = parametros.niteraciones
  ###  Mientra queden iteraciones.
  while ( parametros.niteraciones > 0 )
    parametros.niteraciones -= 1
    
    ### Ejecutar y evaluar cada individuo almacenando el resultado en su campo evaluacion.
    poblacion.each{ |individuo|
      evaluarInd( individuo.codigo, individuo.evaluacion, simbolos.variables, datos.entradas )
      individuo.error = nivelarInd( individuo.evaluacion, individuo.error, datos.salidas ) 
    }
    
    # Ordenacion de los individuos por aptitudes.
    begin
      poblacion = poblacion.sort_by{ |individuo| individuo.error.to_f }
    rescue
      puts "ordenar.. Infinity o NaN"
    end

    # A modo depuracoin voy imprimiendo el estado del sistema.
    puts "G: #{(iterIniciales - parametros.niteraciones)}/#{iterIniciales} | P: #{poblacion.first.codigo} | E: #{poblacion.first.evaluacion} | R: #{poblacion.first.error}"
    
    ### Terminar si hemos encontramos un buen candidato.
    break unless ( poblacion.first.error.to_f > 0.01 )
    
    ### Seleccion de los dos mejores candidatos.
    primero,segundo = *poblacion

    # Eliminacion del resto de individuos.
    poblacion = nil

    ### Generacion de la nueva poblacion conforme a los porcentajes recomendados por John R. Koza.
    poblacion = Array.new

    # Generacion de individuos a partir de mutaciones del mejor.
    for i in 1..( parametros.nindividuos * 0.10 ).to_i
      poblacion.push( Tindividuo.new( generarCodigo( parametros.noperandos, simbolos.funciones, simbolos.variables, simbolos.numeros ), Array.new( datos.salidas.size ), 1 ) )
    end

    # Generacion de individuos mediante cruces entre los dos mejores. 85%
    for i in 1..( parametros.nindividuos * 0.85 ).to_i 
      poblacion.push( Tindividuo.new( cruzarCodigos( primero.codigo, segundo.codigo ), Array.new( datos.salidas.size ), 1 ) )
    end
    
    # Generacion del resto de la poblacion. 4%
    for i in 1..( parametros.nindividuos * 0.04 ).to_i
      poblacion.push( Tindividuo.new( generarCodigo( parametros.noperandos, simbolos.funciones, simbolos.variables, simbolos.numeros ), Array.new( datos.salidas.size ), 1 ) )
    end

    # Reproduccion del mejor individuo. 1%
    poblacion.push( primero )
  end
  
  ### Impresion de resultados.
  puts " "
  puts "Simbolos: Funciones #{simbolos.funciones}, Variables #{simbolos.variables}, Numeros #{simbolos.numeros}"
  puts "Datos: Entradas x0,x1..xn #{datos.entradas}, Salidas y0,y1..yn #{datos.salidas}"
  puts "Parametros: Noperandos #{parametros.nindividuos}, Nindividuos #{parametros.nindividuos}, Niteraciones #{iterIniciales}"
  puts "Leyenda: G:Generacion | P:Programa | E:Evaluacion: f(x0)f(x1)..f(xn) | R:Error"  
end

# Llamada a la rutina principal.

gpsystem( simbolos, datos, parametros )
